package leetcode.dynamic;

public class Lc279 {


    public int numSquares(int n) {
        int[] f = new int[n + 1];
        f[0] = 0;
        for (int i = 1; i <= n ; i++) {
            f[i] = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i ; j++) {
                f[i] = Math.min(f[i], f[i - j * j] + 1);
            }
        }
        return f[n];
    }


    public static void main(String[] args) {
        Lc279 lc279 = new Lc279();
        System.out.println(lc279.numSquares(12));


    }
}
